package com.leetcode.problems055;


/**
 * https://leetcode-cn.com/problems/jump-game/
 * @Date 2021/11/20 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution {


    public boolean canJump(int[] nums) {
        int[] memo = new int[nums.length];
        return canJump(0,nums,memo);
    }

    /**
     * 从i下标跳转,超时了
     * @param i
     * @param nums
     */
    private boolean canJump(int i, int[] nums,int[] memo) {
        if(i >= nums.length - 1){
            return true;
        }
        if(memo[i] != 0){
            return memo[i] == 1;
        }
        for (int j = 1; j <= nums[i]; j++) {
            if(canJump(i + j,nums,memo)){
                memo[i] = 1;
                return true;
            }
        }
        memo[i] = -1;
        return false;
    }

    public static void main(String[] args) {
        int nums[] = {3,2,1,0,4};
        System.out.println(new Solution().canJump(nums));
    }
}
